package leetcode100;

import java.util.Scanner;

/**
 * @author shkstart
 * 请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）
 * 从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，
 * 要求不能走回头路，即：只能往右和往下走，不能往左和往上走。
 *
 * 注：沿棋盘格之间的边缘线行走
 *
 * 数据范围： 1 \le n,m \le 8 \1≤n,m≤8
 * @create 2022-11-29-22:21
 */
public class Meme9_2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int result = way(n,m);
        System.out.println(result);

    }

    /**
     1. 对于上面的n*m(3*3)的格子，有两种情况
     a. 如果n或者m为1，则只有一行或者一列，从左上角走到右下角的路径数为n + m
     比如： 1 * 1格子，可以先向下走，再向右走，到达右下角；或者先向右走，
     再向下走，到达右下角，共两条，即 1 + 1 = 2，对于1 * m和 n * m的
     情况同学们自己画一下
     b. 如果n,m都大于1，那么走到[n][m]格子的右下角只有两条路径，
     <1>: 从[n - 1][m]格子的右下角向下走，到达
     <2>: 从[n][m - 1]格子的右下角向右走，到达
     所以走到[n][m]格子的右下角的数量为[n-1][m] + [n][m - 1],可以通过递归实现，情况a为递归的终止条件。
     */

    private static int way(int n, int m) {
        if(n==1&&m>=1 || m==1&&n>=1){
            return n+m;
        }
        return way(n,m-1)+way(n-1,m);

    }
}
